use rand::Rng;
use rand::distributions::Uniform;
use num_bigint::BigInt;
use num_traits::One;

#[inline]
pub fn fibonacci(n: u64) -> u64 {
    match n {
        0 => 1,
        1 => 1,
        n => fibonacci(n-1) + fibonacci(n-2),
    }
}

fn big_fibonacci(n: u64) -> BigInt {
    let mut a: BigInt = One::one();
    let mut b: BigInt = BigInt::from(1);
    for _ in 0..n {
        let next = a.clone() + b.clone();
        a = b;
        b = next;
    }
    a
}

#[cfg(bench)]
pub fn big_fibonacci_bench(n: u64) -> BigInt{
    big_fibonacci(n)
}


/* 插入排序 - 通过插入到适当位置进行排序
- 从第二个元素开始，与前面的元素比较以找到正确位置并插入。*/
pub fn sort(arr: &mut Vec<i32>, n: usize) {
    for i in 1..n {
        let key = arr[i]; // 当前要插入的整数
        let mut j = (i - 1) as i32;
        while j >= 0 && arr[j as usize] > key {
            arr[(j + 1) as usize] = arr[j as usize];
            j -= 1; // 向左移动进行下一次比较
        }
        arr[(j + 1) as usize] = key;
    }
}

pub fn rand_str(length: usize, str: &str) -> String {
    let str_chars: Vec<char> = str.chars().collect();
    let str_len = str_chars.len();
    let range = Uniform::from(0..str_len);

    let mut rng = rand::thread_rng();
    let mut res = String::new();

    for _ in 0..length {
        let idx = rng.sample(&range);
        res.push(str_chars[idx]);
    }

    res
}

#[test]
fn test_rand_str_() {
    let rs = rand_str(64, "ABCDEFGHIJKLMNOPQRSTUVWXYZ");
    println!("{}", rs);
}

#[test]
fn test_big_fib() {
    println!("{}", big_fibonacci(200));
}
